package traverser;

/* The same algorithm with KeywordFirstTraversal. But this one uses multi-threads.
 * Author: Mark 
 * 
 */

public class KeywordConcurrentTraverser {
	KeyTracker tracker;
	String linkStart;
	String linkEnd;

	public static boolean ifFoundTargetLink = false; // a flag showing if we
														// find the target
	int threadNum; // how many threads will be running
	public static long startTime;
	String[] linksVisited;
	int currentVisitedNum; // record the steps

	public KeywordConcurrentTraverser(String linkStart, String linkEnd,
			int threadNum) {
		startTime = System.currentTimeMillis();
		this.linkStart = linkStart;
		this.linkEnd = linkEnd;
		this.threadNum = threadNum;

		System.out.println("Start: " + linkStart);
		linksVisited = new String[100];
		for (int i = 0; i < 100; i++) {
			linksVisited[i] = "";
		}
		Search();
		currentVisitedNum = 0;
	}

	public void Search() {
		tracker = new KeyTracker(linkEnd); // store the keyword of the end page
											// as hashmap
		String nextLink = linkStart;
		linksVisited[currentVisitedNum++] = nextLink;
		while (ifFoundTargetLink == false) {
			CacheLinkProcessor clp = new CacheLinkProcessor(nextLink);
			clp.removeDuplicates();
			String[] links = clp.getLinks();
			KeywordThread[] linkThread = new KeywordThread[threadNum];

			// Start all the threads
			for (int i = 0; i < threadNum; i++) {
				linkThread[i] = new KeywordThread(links, i, threadNum, tracker,
						linkEnd);
				linkThread[i].start();
			}

			try {
				long tempStart = System.currentTimeMillis();
				for (int i = 0; i < threadNum; i++) {
					if (linkThread[i].interrupted()) { // detect if any thread
														// has interrupted
						ifFoundTargetLink = true;
					}
					linkThread[i].join();
				}
			} catch (Exception e) {
			}

			// if we haven't found the target link, we might need to choose the
			// link with the highest priority as our next link
			if (ifFoundTargetLink == false) {
				int[] p = new int[threadNum];
				String[] nextLinks = new String[threadNum];
				// get the highest-priority links of each threads
				for (int i = 0; i < threadNum; i++) {
					p[i] = linkThread[i].getHighestPriority();
					nextLinks[i] = linkThread[i].getNextlink();
				}
				// sequence these links
				int highestPriority = 0;
				for (int i = 0; i < p.length; i++) {
					for (int j = i + 1; j < p.length; j++)
						if (p[i] < p[j]) {
							int tempPri = p[j];
							String tempLink = nextLinks[j];
							p[j] = p[i];
							nextLinks[j] = nextLinks[i];
							p[i] = tempPri;
							nextLinks[i] = tempLink;
						}
				}

				// choose the one with highest priority and not visited before
				int next = 0;
				nextLink = nextLinks[next];
				highestPriority = p[next++];
				while (IfVisited(nextLink, linksVisited, currentVisitedNum)) {
					nextLink = nextLinks[next];
					highestPriority = p[next++];
				}

				System.out.println("Visit " + nextLink + " with priority of "
						+ highestPriority + "  "
						+ (System.currentTimeMillis() - startTime));
				linksVisited[currentVisitedNum++] = nextLink;
			}
		}
		System.out.println("Found target link " + linkEnd + "  "
				+ (System.currentTimeMillis() - startTime));
	}

	public boolean IfVisited(String link, String[] visitedLink, int visitedNum) {
		boolean ifVisited = false;
		for (int i = visitedNum - 1; i >= 0; i--) {
			if (link.equals(visitedLink[i]))
				ifVisited = true;
		}
		return ifVisited;
	}

	public static void main(String[] args) {
		String link_start = "http://en.wikipedia.org/wiki/The_Lord_of_the_Rings";
		String link_end = "http://en.wikipedia.org/wiki/Turkish_Cypriots";
		final int threads = 20;
		KeywordConcurrentTraverser k = new KeywordConcurrentTraverser(
				link_start, link_end, threads);

	}

}
